#include <iostream>
#include <algorithm>
#include <cassert>

#include "../util.h"
#include "tm.h"

using std::list;
using std::ostream;
using std::istream;
using std::cout;
using std::cerr;
using std::endl;

const size_t MAX_PHRASE_LENGTH = 3;

// вспомогательная функция читает предложение из потока и добавляет соответствующую конструкцию в хвост списка AllSent
bool TRawReader::ReadNextSent() {
    string str, str2, str3;
    if (!getline(Input, str)) {
        return false;
    }

    AllSent.push_back(TRawSent());
    TRawSent& sent = AllSent.back();
    sent.SentId = NextSentId;
    sent.Text = str;
    ++NextSentId;

    // разбиваем на слова и заносим слова в TRawSent.Words
    vector<string> words = SplitString(str);
    for (size_t i = 0; i < words.size(); ++i) {
        sent.Words.push_back(TRawNode(i, words[i]));
    }
    if (words.empty()) {
        return false;
    }

    // читаем соответствующее предложение из GizaInput
    if (!(getline(GizaInput, str) &&
          getline(GizaInput, str2) &&
          getline(GizaInput, str3))) {
        throw TException("cannot read next sent from giza");
    }

    // удаляем пробелы на конце
    RTrim(str3);

    // заносим выравнивание в массив TRawSent.GizaPoints
    sent.GizaPoints.resize(sent.Words.size());
    vector<string> tokens = SplitString(str3);
    int wordCount = -1;
    bool openbr = false;
    for (vector<string>::const_iterator it = tokens.begin(); it != tokens.end(); ++it) {
        if (it->compare("({") == 0) {
            openbr = true;
        } else if (it->compare("})") == 0) {
            openbr = false;
        } else if (openbr) {
            int id = FromString<int>(*it);
            sent.GizaPoints[id - 1] = wordCount - 1;
        } else {
            ++wordCount;
        }
    }
    return true;
}

// считать n предложений из потока
size_t TRawReader::ReadNSent(size_t n) {
    AllSent.clear();
    size_t i;
    for (i = 0; i < n; ++i) {
        if (!ReadNextSent()) {
            break;
        }
    }
    return i;
}

// открывает поток Input и GizaInput
void TRawReader::Open(const string& filename, const string& gizaFilename) {
    Input.open(filename.c_str());
    NextSentId = 0;
    GizaInput.open(gizaFilename.c_str());
}

// закрывает поток Input и GizaInput
void TRawReader::Close() {
    Input.close();
    GizaInput.close();
}

void TPhraseExtractor::InitAlignment() {
    // устанавливаем размер матрицы
    Matrix.resize(SentRu->Words.size());
    for (size_t i = 0; i < Matrix.size(); ++i) {
        Matrix[i].resize(SentEn->Words.size());
        std::fill(Matrix[i].begin(), Matrix[i].end(), None);
    }

    // заполняем матрицу
    for (size_t i = 0; i < SentRu->GizaPoints.size(); ++i) {
        int j = SentRu->GizaPoints[i];
        if (j >= 0) {
            Matrix[i][j] |= RuEn;
        }
    }

    for (size_t j = 0; j < this->SentEn->GizaPoints.size(); ++j) {
        int i = SentEn->GizaPoints[j];
        if (i >= 0) {
            Matrix[i][j] |= EnRu;
        }
    }
}

// Извлекает из предложений параллельные фразы, которые не противоречат пословным соответствиям Гизы (Matrix).
// Фразы состоят из слов, идущих в предложении подряд, максимальное количество слов во фразе = maxPhraseLength
list<TAlignedPhrase> TPhraseExtractor::ExtractPhrases(size_t maxPhraseLength) const {
    list<TAlignedPhrase> alignedPhrases; // здесь будут храниться извлеченные фразы
    size_t countRu = SentRu->Words.size();
    size_t countEn = SentEn->Words.size();
    // вспомогательный вектор: сколько русских слов сопоставлено каждому английскому слову
    vector<size_t> alignedCountEn(countEn);
    // вспомогательный вектор векторов: какие английские слова сопоставлены каждому русскому слову
    vector< vector<size_t> > alignedToRu(countRu);
    // заполняем вспомогательные вектора
    for (size_t i = 0; i < Matrix.size(); ++i) {
        for (size_t j = 0; j < Matrix[i].size(); ++j) {
            if (Matrix[i][j] != None) {
                ++alignedCountEn[j];
                alignedToRu[i].push_back(j);
            }
        }
    }

	// перебираем все возможные фразы [startRu..endRu] из русского предложения не длиннее maxPhraseLength
    for (size_t startRu = 0; startRu < countRu; ++startRu) {
        for (size_t endRu = startRu; (endRu < countRu) && (endRu < startRu + maxPhraseLength); ++endRu) {
            int minEn = 9999;
            int maxEn = -1;
            vector<size_t> usedEn = alignedCountEn; //для каждого сопоставленного английского слова будем уменьшать счетчик в соответствующей позиции
			//перебираем английские слова, сопоставленные словам из отрезка [startRu..endRu], находим самое левое(minEn) и самое правое(maxEn)
            for (size_t ei = startRu; ei <= endRu; ++ei) {
                for (size_t i = 0; i < alignedToRu[ei].size(); ++i) {
                    int fi = alignedToRu[ei][i];
                    if (fi < minEn) {
                        minEn = fi;
                    }
                    if (fi > maxEn) {
                        maxEn = fi; 
                    }
                    --usedEn[fi];
                }
            }
			// проверяем, что в русской фразе [startRu..endRu] установлено английское соответствие хотя бы для одного слова 
            // и что длина английской фразы [minEn...maxEn] не превышает maxPhraseLength
            if ((maxEn < 0) || (maxEn - minEn >= (int)maxPhraseLength)) { 
                continue;
            }
            // проверяем, что никакое из слов английской фразы не сопоставлено никакому русскому слову за границами параллельной фразы 
            bool outOfBounds = false;
            for (size_t fi = minEn; fi <= (size_t)maxEn && !outOfBounds; ++fi) {
                if (usedEn[fi] > 0) {
                    outOfBounds = true;
                }
            }
            if (outOfBounds) {
                continue;
            }

            // фразы могут присоединять невыровненные "ничейные" слова спереди и сзади
            for (int startEn = minEn;
                 (startEn >= 0) &&
                     (startEn + maxPhraseLength > (size_t)maxEn) && // не длиннее максимальной длины фразы
                     ((startEn == minEn) || (alignedCountEn[startEn] == 0)); // учесть невыровненные
                 --startEn)
            {
                for (int endEn = maxEn;
                    ((size_t)endEn < countEn && 
                        (size_t)endEn < startEn + maxPhraseLength && // не длиннее максимальной длины фразы
                        (endEn == maxEn || alignedCountEn[endEn] == 0)); // учесть невыровненные
                    ++endEn)
                {
                    TAlignedPhrase phrase;
                    for (size_t i = startRu; i <= endRu; ++i) {
                        phrase.RuPhrase += SentRu->Words[i].Form + ' ';
                    }
                    for (size_t i = startEn; i <= (size_t)endEn; ++i) {
                        phrase.EnPhrase += SentEn->Words[i].Form + ' ';
                    }
                    RTrim(phrase.RuPhrase);
                    RTrim(phrase.EnPhrase);
                    assert(!phrase.RuPhrase.empty());
                    assert(!phrase.EnPhrase.empty());
                    alignedPhrases.push_back(phrase);
                }
            }
        }
    }
    return alignedPhrases;
}

// распечатать матрицу
void TPhraseExtractor::DebugPrintAlignment(ostream& out) const {
    for (size_t i = 0; i < Matrix.size(); ++i) {
        for (size_t j = 0; j < Matrix[i].size(); ++j) {
            out << (int)Matrix[i][j] << ' ';
        }
        out << '\n';
    }
}

void ProcessOneSentencePair(const TRawSent& rawSentRu, const TRawSent& rawSentEn, 
                            TPhraseMatching& phraseMatching, ostream& out)
{
    out << "***" << '\n';
    out << rawSentRu.Text << '\n';
    out << rawSentEn.Text << '\n';
    TPhraseExtractor phraseExtractor(&rawSentRu, &rawSentEn);
    phraseExtractor.InitAlignment();
    phraseExtractor.DebugPrintAlignment(out);
    list<TAlignedPhrase> alignedPhrases = phraseExtractor.ExtractPhrases(MAX_PHRASE_LENGTH);
    out <<  "**** extracted phrases" << '\n';
    for (list<TAlignedPhrase>::const_iterator it = alignedPhrases.begin(); it != alignedPhrases.end(); ++it) {
        out << it->EnPhrase << " ||| " << it->RuPhrase << '\n';
        ++phraseMatching.RuPhraseFreq.dict[it->RuPhrase];
        ++phraseMatching.EnPhraseFreq.dict[it->EnPhrase];
		++phraseMatching.Translations[it->RuPhrase].dict[it->EnPhrase];
    }
    out << '\n';
}

// формат вывода: см. ReadPhraseMatching в интерфейсе
ostream& operator<<(ostream& out, const TPhraseMatching& phraseMatching) {
    for (map<string, TFreqDict>::const_iterator ruIterator = phraseMatching.Translations.begin();
         ruIterator != phraseMatching.Translations.end();
         ++ruIterator)
    {
        string ruPhrase = ruIterator->first;
        size_t ruFreq = phraseMatching.RuPhraseFreq.dict.find(ruPhrase)->second;
        for (TFreqDictPart::const_iterator enIterator = ruIterator->second.dict.begin();
             enIterator != ruIterator->second.dict.end();
             ++enIterator)
        {
            string enPhrase = enIterator->first;
            size_t pairFreq = enIterator->second;
            size_t enFreq = phraseMatching.EnPhraseFreq.dict.find(enPhrase)->second;
            out << enPhrase << " ||| " << ruPhrase << " ||| " << enFreq << ' ' << ruFreq << ' ' << pairFreq << '\n';
        }
    }
    return out;
}

istream& operator>>(istream& in, TPhraseMatching& phraseMatching) {
    string line;
    while (getline(in, line)) {
        vector<string> macroTokens = SplitString(line, " ||| ");
        assert(macroTokens.size() == 3);
        string enPhrase = macroTokens[0];
        string ruPhrase = macroTokens[1];
        vector<string> frequencies = SplitString(macroTokens[2]);
        assert(frequencies.size() == 3);
        phraseMatching.EnPhraseFreq.dict[enPhrase] = FromString<size_t>(frequencies[0]);
        phraseMatching.RuPhraseFreq.dict[ruPhrase] = FromString<size_t>(frequencies[1]);
		phraseMatching.Translations[ruPhrase].dict[enPhrase] = FromString<size_t>(frequencies[2]);
    }
    return in;
}

void ProcessFiles(const TFileNames& filenames, TRawReader& rawReaderRu, TRawReader& rawReaderEn) {
    // открываем потоки для чтения предложений
    rawReaderRu.Open(filenames.RawNameRu, filenames.GizaNameRuEn);
    rawReaderEn.Open(filenames.RawNameEn, filenames.GizaNameEnRu);
    std::ofstream out(filenames.OutName.c_str());
    TPhraseMatching phraseMatching;

    // предложения в файлах Гизы и raw-файлах должны соответствовать один к одному
    while (true) {
        if ((rawReaderRu.ReadNSent(1) == 0) ||
                (rawReaderEn.ReadNSent(1) == 0))
        {
            break;
        }
        TRawSent& rawSentRu = rawReaderRu.AllSent.back();
        TRawSent& rawSentEn = rawReaderEn.AllSent.back();
        ProcessOneSentencePair(rawSentRu, rawSentEn, phraseMatching, cout);
    }

    out << phraseMatching;

    rawReaderRu.Close();
    rawReaderEn.Close();
}
